package com.zy.recursion;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @description: 斐波那契数
 * @author: zhaoyi
 * @create: 2019-09-03 22:40
 * https://leetcode-cn.com/explore/orignial/card/recursion-i/258/memoization/1212/
 **/

public class FibonacciNum {

    //递归一定注意避免重复计算
    private int [] list;

    /**
     * F(0) = 0,
     * F(1) = 1
     * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
     * @param N
     * @return
     */
    public int fib(int N) {
        list = new int[N+1];
        return recufib(N);
    }

    private int recufib(int n){
        if (n <= 1) {
            return n;
        } else if (list[n] > 0){
            return list[n];
        }else {
            int result = recufib(n - 1) + recufib(n - 2);
            list[n] = result;
            return result;
        }
    }

}
